#pragma once
#include "unordered_map"
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *  LC695/LC827/LC463/LC200
 *  加油直接编辑器刷题
 * */

int maxV=0;
vector<vector<bool>> used;//设置已经用的
//因为这个东西需要遍历所有 所以不设置返回值
void numIslands_r(vector<vector<char>>& grid,int row,int col,int rowSize,int colSize,int &pre) {

    if (row>rowSize||col>colSize || row<0|| col<0 )
        return;
    if (grid[row][col]!='1'){
        return;
    }

    if (used[row][col])
        return;
    used[row][col]= true;

    if (grid[row][col]=='1'){
        pre=1;;
    }

    //原来想他会不会重复一直搜索。。导致死循环 太久没做dfs 有点傻逼 因为这四行有限 他上下左右走完不会一直走了
    numIslands_r(grid,row+1,col,rowSize,colSize,pre);
    numIslands_r(grid,row,col+1,rowSize,colSize,pre);
    numIslands_r(grid,row-1,col,rowSize,colSize,pre);
    numIslands_r(grid,row,col-1,rowSize,colSize,pre);

}


int numIslands(vector<vector<char>>& grid) {
    int rowSize=grid.size()-1;
    int colSize=grid[0].size()-1;
    used.resize(rowSize+2,vector<bool>(colSize+2, false));
    for (int i = 0; i <=rowSize ; ++i) {

        for (int j = 0; j <=colSize ; ++j) {

            if ( used[i][j])
                continue;
            int pre=0;
            numIslands_r(grid,i,j,rowSize,colSize,pre);
            if (pre){
                maxV++;
            }


        }

    }


    return maxV;
}